|
Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes. Research in polyhedral combinatorics falls into two distinct areas. Mathematicians in this area study the combinatorics of polytopes; for instance, they seek inequalities that describe the relations between the numbers of vertices, edges, and faces of higher dimensions in arbitrary polytopes or in certain important subclasses of polytopes, and study other combinatorial properties of polytopes such as their connectivity and diameter (number of steps needed to reach any vertex from any other vertex). Additionally, many computer scientists use the phrase “polyhedral combinatorics” to describe research into precise descriptions of the faces of certain specific polytopes (especially 0-1 polytopes, whose vertices are subsets of a hypercube) arising from integer programming problems. ==Faces and face-counting vectors== A ''face'' of a convex polytope ''P'' may be defined as the intersection of ''P'' and a closed halfspace ''H'' such that the boundary of ''H'' contains no interior point of ''P''. The dimension of a face is the dimension of this hull. The 0-dimensional faces are the vertices themselves, and the 1-dimensional faces (called ''edges'') are line segments connecting pairs of vertices. Note that this definition also includes as faces the empty set and the whole polytope ''P''. If ''P'' itself has dimension ''d'', the faces of ''P'' with dimension ''d'' − 1 are called ''facets'' of ''P'' and the faces with dimension ''d'' − 2 are called ''ridges''.〔, p. 51.〕 The faces of ''P'' may be partially ordered by inclusion, forming a face lattice that has as its top element ''P'' itself and as its bottom element the empty set. A key tool in polyhedral combinatorics is the ''ƒ-vector'' of a polytope,〔, pp. 245–246.〕 the vector (''f''0, ''f''1, ..., ''f''''d'' − 1) where ''fi'' is the number of ''i''-dimensional features of the polytope. For instance, a cube has eight vertices, twelve edges, and six facets, so its ƒ-vector is (8,12,6). The dual polytope has a ƒ-vector with the same numbers in the reverse order; thus, for instance, the regular octahedron, the dual to a cube, has the ƒ-vector (6,12,8). The ''extended ƒ-vector'' is formed by concatenating the number one at each end of the ƒ-vector, counting the number of objects at all levels of the face lattice; on the left side of the vector, ''f''-1 = 1 counts the empty set as a face, while on the right side, ''fd'' = 1 counts ''P'' itself. For the cube the extended ƒ-vector is (1,8,12,6,1) and for the octahedron it is (1,6,12,8,1). Although the vectors for these example polyhedra are unimodal (the coefficients, taken in left to right order, increase to a maximum and then decrease), there are higher-dimensional polytopes for which this is not true.〔, p. 272.〕 For simplicial polytopes (polytopes in which every facet is a simplex), it is often convenient to transform these vectors, producing a different vector called the ''h''-vector. If we interpret the terms of the ƒ-vector (omitting the final 1) as coefficients of a polynomial ƒ(''x'') = Σ''fix''''d'' − ''i'' − 1 (for instance, for the octahedron this gives the polynomial ƒ(''x'') = ''x''3 + 6''x''2 + 12''x'' + 8), then the ''h''-vector lists the coefficients of the polynomial ''h''(''x'') = ƒ(''x'' − 1) (again, for the octahedron, ''h''(''x'') = ''x''3 + 3''x''2 + 3''x'' + 1).〔, pp. 246–253.〕 As Ziegler writes, “for various problems about simplicial polytopes, ''h''-vectors are a much more convenient and concise way to encode the information about the face numbers than ƒ-vectors.” 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「polyhedral combinatorics」の詳細全文を読む スポンサード リンク
|